package uniquePaths;

import java.util.HashMap;
import java.util.Objects;

public class Solution {
    public static void main(String[] args) {
        System.out.println(uniquePaths(3, 4));
    }

    //已经计算过3*4或者4*3的
    static int[][]arr=new int[100][100];
    public static int uniquePaths(int m, int n) {

        if(arr[m][n]!=0){
         return arr[m][n];
        }
        if(m==1||n==1){
            return 1;
        }
        int res=uniquePaths(m-1,n)+uniquePaths(m,n-1);
        arr[m][n]=res;
        return res;
    }
}


//class Solution {
//    public int uniquePaths(int m, int n) {
//        int[][] f = new int[m][n];
//        for (int i = 0; i < m; ++i) {
//            f[i][0] = 1;
//        }
//        for (int j = 0; j < n; ++j) {
//            f[0][j] = 1;
//        }
//        for (int i = 1; i < m; ++i) {
//            for (int j = 1; j < n; ++j) {
//                f[i][j] = f[i - 1][j] + f[i][j - 1];
//            }
//        }
//        return f[m - 1][n - 1];
//    }
//}
//
//作者：LeetCode-Solution
//        链接：https://leetcode.cn/problems/unique-paths/solution/bu-tong-lu-jing-by-leetcode-solution-hzjf/
//        来源：力扣（LeetCode）
//        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

//class Solution {
//    public int uniquePaths(int m, int n) {
//        long ans = 1;
//        for (int x = n, y = 1; y < m; ++x, ++y) {
//            ans = ans * x / y;
//        }
//        return (int) ans;
//    }
//}
//
//作者：LeetCode-Solution
//        链接：https://leetcode.cn/problems/unique-paths/solution/bu-tong-lu-jing-by-leetcode-solution-hzjf/
//        来源：力扣（LeetCode）
//        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。